/**
 * 给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
 *
 * 设计一个算法使得这 m 个子数组各自和的最大值最小
 * https://leetcode.cn/problems/split-array-largest-sum/
 * 思路：和1011.在D天内送达包裹的能力的思路差不多
 * 不信的话，把上面的题翻译一下，货船每天运走的货物就是nums的一个子数组，在m天内运完就是将nums划分成m个子数组，让货船的载重尽可能小，
 * 就是让所有子数组中最大的那个子数组元素之和尽可能小
 * 详解：https://labuladong.gitee.io/algo/2/20/31/
 */


class SqplitArray {
    public int splitArray(int[] nums, int m) {
        int left=0;
        int right=1;
        for(int num:nums) {
            left=Math.max(num,left);
            right+=num;
        }
        while(left<right) {
            int mid=left+((right-left)>>>1);
            if(f(mid,nums)<m) {
                right=mid;
            } else if(f(mid,nums)>m) {
                left=mid+1;
            } else {
                right=mid;
            }
        }
        return left;
    }
    public int f(int x,int[] weights) {
        int days=0;
        int len=weights.length;
        int i=0;
        while(i<len) {
            int cap=x;
            while(i<len) {
                if(weights[i]>cap) {
                    break;
                } else {
                    cap-=weights[i];
                    i++;
                }
            }
            days++;
        }
        return days;
    }
}